/*-------------------------------------------------------------------------*/
/**
  @file		pq_dll.c
  @author	Renaud Wanschoor
  @date	july 2004
  @version	$Revision: 2.8 $
  @brief	dll implementation of priority queues

  prototypes are to be found in prototypes.h
  
*/
/*--------------------------------------------------------------------------*/
#include "plib.h"

/************************************************************************/

typedef struct HeapElt{
  double gain;
  struct HeapElt* p;	/* previous in list */
  struct HeapElt* n;	/* next in list */
}HeapElt;

static void HeapMoveDown(Heap* h,HeapElt* elt);
static void HeapMoveUp(Heap* h,HeapElt* elt);

/************************************************************************/

void HeapInit(Mem* farm, Heap* h,int size){
  h->type   = HEAP_DLL;
  h->farm   = farm;
  h->mem    = NULL;

  h->s     = 0;
  h->max_s = size;

  h->pos    = NULL;	/* not used */
  h->h      = NULL;
  
  MEM_Need(farm, size, HeapElt);
}

/************************************************************************/

void HeapClean(Heap* h){
  int i;
  int    max_s = h->s;
  HeapElt* mem = h->mem;

  for(i=0;i<max_s;i++){
    
    mem[i].gain = -INFINITY;
    mem[i].n    = NULL;
    mem[i].p    = NULL;
  }

  h->s = 0;
  h->h = NULL;
}

/************************************************************************/

void HeapFree(Heap* h){
  h->s      = 0;
  h->max_s  = 0;
  h->h      = NULL;
  h->mem    = NULL;
  h->farm   = NULL;
}

/***********************************************************************/

int HeapInsert(Heap* h,double gain){
  HeapElt* heap_m = h->mem;
  int idx = h->s++;

  if(heap_m == NULL)
    heap_m = h->mem = MEM_Request(h->farm, h->max_s, HeapElt);

  if(h->s<=h->max_s){
    heap_m[idx].gain = gain;
    heap_m[idx].p    = NULL;
    if((heap_m[idx].n = (HeapElt*)h->h) != NULL)
      heap_m[idx].n->p = &(heap_m[idx]);
    h->h = &(heap_m[idx]);

    if(heap_m[idx].n != NULL && heap_m[idx].n->gain > gain){
      h->h = heap_m[idx].n;
      HeapMoveDown(h,&(heap_m[idx]));
    }
    return &(heap_m[idx]) - heap_m;
  }

  ERROR((1,"HeapInsert error code 1 : heap to small, maximum size is %d\n",h->max_s));
  return -1;
}

/**********************************************************************/

void HeapRemove(Heap* h, int epos){
  HeapElt* elt = &(((HeapElt*)h->mem)[epos]);

  if(elt->p != NULL || elt->n != NULL || h->h == elt){
    if(elt->p == NULL)
      h->h = elt->n;
    else
      elt->p->n = elt->n;
    if(elt->n != NULL)
      elt->n->p = elt->p;
  }

  if(epos != h->s - 1){
    *elt = ((HeapElt*)h->mem)[h->s-1];
    if(elt->p !=NULL || elt->n != NULL || h->h == &(((HeapElt*)h->mem)[h->s-1])){
      if(elt->p == NULL)
	h->h = elt;
      else
	elt->p->n = elt;
      if(elt->n != NULL)
	elt->n->p = elt;
    }
  }
  h->s--;
}

/**********************************************************************/

void HeapUpdate(Heap* h, int epos, double gain){
  HeapElt*  elt = &(((HeapElt*)h->mem)[epos]);
  HeapElt* next = elt->n;
  HeapElt* prev = elt->p;

  elt->gain = gain;

  if(prev != NULL && prev->gain < gain){
    HeapMoveUp(h,elt);
    return;
  }
  if(next != NULL && next->gain > gain){
    if(prev == NULL)
      h->h = elt->n;
    HeapMoveDown(h,elt);
  }
}

/**************************************************************************/

double HeapSeeHead(Heap* h){
  if(h->h == NULL)
    return -INFINITY;
  return ((HeapElt*)h->h)->gain;
}

/**************************************************************************/

int HeapGetHead(Heap* h){
  if(h->h == NULL)
    return -1;

  return (HeapElt*)h->h - (HeapElt*)h->mem;
}

/**************************************************************************/

void   HeapUpdateHead(Heap* h){
  HeapElt* head = h->h;
  head->gain *= -1;
  
  if(head->n != NULL && head->gain < head->n->gain){
    h->h = head->n;
    HeapMoveDown(h,head);
  }
}

/**************************************************************************/

int HeapRemoveHead(Heap* h){ 
  HeapElt* elt = h->h;
  if(elt == NULL)
    return -1; 
  
  if((h->h = elt->n) != NULL)
    elt->n->p = NULL;

  elt->n = NULL;
  elt->p = NULL;
    
  return elt - (HeapElt*)h->mem;
}

/**************************************************************************/

double HeapGetGain(Heap* h,int epos){
  return ((HeapElt*)h->mem)[epos].gain;
}

/**************************************************************************/
/**************************** PRIVATE FUNCTIONS ***************************/
/**************************************************************************/

void HeapMoveDown(Heap* h,HeapElt* elt){
  HeapElt* next = elt->n;
  HeapElt* prev = elt->p;

  elt->n = next->n;
  elt->p = next;
  if(prev != NULL)
    prev->n = next;
  next->p = prev;
  next->n = elt;

  if(elt->n != NULL){
    elt->n->p = elt;
    if(elt->n->gain > elt->gain)
      HeapMoveDown(h,elt);
  }
}
void HeapMoveUp(Heap* h, HeapElt* elt){
  HeapElt* next = elt->n;
  HeapElt* prev = elt->p;
    
  elt->p = prev->p;
  elt->n = prev;
  if(next != NULL)
    next->p = prev;
  prev->n = next;
  prev->p = elt;

  if(elt->p == NULL)
    h->h = elt; 
  else {
    elt->p->n = elt;
    if(elt->p->gain < elt->gain)
      HeapMoveUp(h,elt);
  }
}

/**************************************************************************/
/****************************** DEBUGGING *********************************/
/**************************************************************************/

//#ifdef DEBUG
int    HeapPos(Heap* h,int idx){
  int i;
  HeapElt* elt = h->h;
  for(i=0;i<idx && elt!=NULL;i++)
    elt = elt->n;

  if(elt == NULL)
    return -1;

  return elt - ((HeapElt*)h->mem);
}
double HeapGain(Heap* h, int idx){
  int i;
  HeapElt* elt = h->h;
  for(i=0;i<idx && elt!=NULL;i++)
    elt = elt->n;

  if(elt == NULL)
    return -INFINITY;

  return elt->gain;
}

void HeapPrint(Heap* h){
  HeapElt* elt = h->h;
  int i=0;

  if(elt == NULL)
    return;

  do{
    printf("%3d %10.2f (%2d) %p p : %p n : %p\n",
	   i++,elt->gain,elt - ((HeapElt*)h->mem),
	   elt,elt->p,elt->n);
    elt = elt->n;
  }while(elt != NULL);

}
//#endif
